package org.company.earth.arithmetic;

public class Arithmetic {
    
    /*
     * 分治算法
     * square coins问题处理,
     * 硬币的值 = 硬币边^2, 1 , 4, 9 , 16 ...
     * @param amount
     * @param max square 
     */
    public Integer divideAndConquer(Integer amount,Integer max) {
        if(amount == 1 || max == 1)
            return 1;
        
        while(amount < max*max) {
            max--;
        }
        
        Integer sum = 0;
        Integer k = 0;
        while(amount - k*max*max >= 0){
            sum += this.divideAndConquer(amount-k*max*max, max-1);
            if(max == 1)
                break;
            k++;
        }
        return sum;
    }
    
    public static void main(String[] args) {
        Arithmetic arith = new Arithmetic();
        System.out.println(arith.divideAndConquer(3, 2));
    }
    
}
